package BNS.graphs;

import java.awt.Dimension;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
/* @Author: JSJudd 2006 October
 *
 * This code is useful for laying out simple graphs. It attempts to spread out
 * nodes for better visualization, and is successful on stars and cycles.
 * It has no intrinsic ability to detect or reveal planarity.
 * It will not attempt to jump a node over an edge to find more white space.
 
 Ideas for improvement:
	* define congestion around node in terms of distance to edges as well as
	distance to other nodes. Also include number of edge crossings.
	* calculate congestion in each position of a ring around each node
	and move toward the best.
	* add a speedstroke to select next node
*/
import java.util.Enumeration;
import java.util.Hashtable;


public class LayoutMaker extends GraphPanel implements Runnable, 
								MouseMotionListener, MouseListener {
	/**
   * 
   */
  private static final long serialVersionUID = 1L;
  private Thread relaxer;
    private boolean relaxing;
    boolean random;
	private Creator creator;
	private Dimension appletgPanelSize;
		
	/** constructor that takes a Graph and prepares to build a layout for it.
		The Creator parameter is assumed to be non-null, and that this tool is being
		used to inspect and lay out or change a graph. The Creator will be notified  of 
		the node selected by user mouse actions through its nodePickChanged() method.
		@param c the tool that needs to know which node is selected. */
    public LayoutMaker(Creator c) {
		super(ColorMap.identity());
		creator= c;
		creating= true;
		addMouseListener(this);
		addMouseMotionListener(this);
		waitMessage= "LayoutMaker created";
		appletgPanelSize= new Dimension(500,450);	// estimated size of graphPanel in applet
		}
	
	private Dimension getVirtualWindowSize() {
		if (graph.eigenNode==null) return getSize();
		else return appletgPanelSize;
		}
	
	/** Repeatedly calls the runRelax() method and pauses 5 milliseconds
		until the "relaxing" variable is turned off.
		*/
    public void run() {
		System.err.println("LayoutMaker run()"); 
		while (relaxing) {
			//System.err.println("LayoutMaker size "+ getSize()); 
			//System.err.print("."); 
			relax();
			if (random && (Math.random() < 0.03)) {
				Node n= graph.nodes.elementAt(
								(int)(Math.random() * graph.numNodes()));
				if (!n.fixed) {
					n.x+= 100*Math.random() - 50;
					n.y+= 100*Math.random() - 50;
					}
				//persona.playSound("audio/drip.au");
				}
			repaint();	// remove?
			try { Thread.sleep(5); } 
			catch (InterruptedException e) {break;}
			}
		System.err.println("done"); 
		relaxer= null;
		}
	
	synchronized void scramble() {
		Dimension window= getVirtualWindowSize();
		//System.err.println("graph "+ graph.partial);
		Enumeration<Node> eno= graph.enumNodes();
		while (eno.hasMoreElements()) {
			Node n= eno.nextElement();
			if (!n.fixed) {
				if (n==graph.eigenNode) {
					n.x= 0;  n.y= 0; } // central node
				else {	// place other nodes randomly
					n.x= (window.width -2*nodeRadius)*(Math.random()-0.5);
					n.y= (window.height-2*nodeRadius)*(Math.random()-0.5);
					}
				}
			//System.err.println(n==graph.eigenNode+" "+n.fixed+" "+n+" @("+n.x+", "+n.y+")");
			n.dx= n.dy= 0;
			}
		//System.err.println("LayoutMaker scrambled");
		repaint();
		}
	
	synchronized void shake() {	// jiggle every node position by a little
		Enumeration<Node> eno= graph.enumNodes();
		while (eno.hasMoreElements()) {
			Node n= eno.nextElement();
			if (!n.fixed) {
				n.x += 80*Math.random() - 40;
				n.y += 80*Math.random() - 40;
				}
			n.dx= n.dy= 0;
			}
		repaint();
		}
	
    synchronized void relax() {
		// Separate every node from others nearby.
		Enumeration<Node> eno1= graph.enumNodes();
		while (eno1.hasMoreElements()) {
			Node n1= eno1.nextElement();
			n1.dx=0; n1.dy=0;
			Enumeration<Node> eno2= graph.enumNodes();
			while (eno2.hasMoreElements()) {
				Node n2= eno2.nextElement();
				if (n2==n1) continue;
				double nndx= n2.x - n1.x;
				double nndy= n2.y - n1.y;
				double nnd= Math.sqrt(nndx*nndx + nndy*nndy);
				if(nnd < 2.5*nodeRadius) {
					n1.dx-= 3*nndx/nnd;
					n1.dy-= 3*nndy/nnd;
					//System.err.println(n1 +" repelled from "+ n2 +"  dx="+n1.dx +"  dy="+n1.dy);
					}
				}
			}
		// Find nodes near edges.
		eno1= graph.enumNodes();
		while (eno1.hasMoreElements()) {
			Node n1= eno1.nextElement();
			Enumeration<Edge> ene= graph.enumEdges();
			while (ene.hasMoreElements()) {
				Edge e= ene.nextElement();
				if (e.to==n1 || e.from==n1) continue;	// skip your own edges
				double eedx= e.to.x - e.from.x;
				double eedy= e.to.y - e.from.y;
				double eed= Math.sqrt(eedx*eedx + eedy*eedy);
	//System.err.println("edge "+ e +"  dx="+eedx +" dy="+eedy +" eed="+eed +" eea="+eea);
				double endx= n1.x - e.from.x;
				double endy= n1.y - e.from.y;
				double end= Math.sqrt(endx*endx + endy*endy);
	//System.err.println("\t"+ n1 +" endx="+endx +" endy="+endy+" end="+end+" ena="+ena);
				double cosAlpha= (eedx*endx + eedy*endy)/(eed*end);
				double alpha= Math.acos(cosAlpha);
				double along= end*cosAlpha;
				double away= end*Math.sin(alpha);
	//System.err.println("\tcosAlpha="+cosAlpha +" alpha="+alpha +" along="+along +" away="+away);
				if(along>nodeRadius && along<eed-nodeRadius && away<1.2*nodeRadius) {
					// Move node away from nearby edge.
					double eea= Math.atan2(eedx,eedy);
					double ena= Math.atan2(endx,endy);
	//System.err.printf("edge %s ee=(%.2f,%.2f) eed=%.2f eea=%.3f%n", e,eedx,eedy,eed,eea);
	//System.err.printf("\t%s en=(%.2f,%.2f) end=%.2f ena=%.3f%n", n1,endx,endy,end,ena);
	//System.err.printf("\tcos=%.4f alpha %.4f along %.2f away %.2f%n", cosAlpha,alpha,along,away);
					double diff= (eea-ena + 9*Math.PI/2)%(2*Math.PI);
					int sign= diff>(Math.PI/2)? +1:-1;
					//System.err.printf("\tdiff angle= %.3f, sign=%d%n", diff,sign);
					n1.dx-= 2*eedy/end *sign;
					n1.dy+= 2*eedx/end *sign;
					//System.err.printf("%s repelled from %s (%.2f,%.2f)%n", n1,e,n1.dx,n1.dy);
					// Move edge away from nearby node.
					double balance= along/eed;
					e.to.dx+= 2*eedy/end *sign *balance;
					e.to.dy-= 2*eedx/end *sign *balance;
					e.from.dx+= 2*eedy/end *sign *(1-balance);
					e.from.dy-= 2*eedx/end *sign *(1-balance);
					/*System.err.printf(
							"line repelled %.2f  to.dx=%.2f .dy=%.2f  from.dx=%.2f .dy=%.2f%n",
							balance, e.to.dx, e.to.dy, e.from.dx, e.from.dy);/**/
					}
				}
			//System.err.println();
			}
		// Move every node by amount suggested
		Dimension window= getVirtualWindowSize();
		int maxWide= window.width/2-nodeRadius;
		int maxHigh= window.height/2-nodeRadius;
		eno1= graph.enumNodes();
		while (eno1.hasMoreElements()) {
			Node n= eno1.nextElement();
			if (!n.fixed) {
				n.x+= Math.max(-5, Math.min(5, n.dx));
				n.y+= Math.max(-5, Math.min(5, n.dy));
				//System.out.println("v= " + n.dx + "," + n.dy);
				if (n.x < -maxWide) n.x= -maxWide;  else if (n.x > maxWide) n.x= maxWide;
				if (n.y < -maxHigh) n.y= -maxHigh;  else if (n.y > maxHigh) n.y= maxHigh;
				}
			}
		repaint();
		}
	
    boolean pickfixed;
	
	/** required by MouseListener interface */
    public void mousePressed(MouseEvent event) {
		//System.err.println("mousePressed "+ event);
		addMouseMotionListener(this);
		//double bestdist= Double.MAX_VALUE;
		int x= event.getX()-translateX, y=event.getY()-translateY;
/*		Enumeration eno= graph.enumNodes();
		while (eno.hasMoreElements()) {
			Node n= eno.nextElement();
			double dist= (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
			//System.err.println(n +" @("+ n.x +", "+ n.y +") dist="+ dist);
			if (dist < bestdist) { bestdist= dist; pick= n; }
			}*/
		pick= graph.select(x,y);	// TODO: what if pick==null ??
		pickfixed= pick.fixed;
		if (creator!=null) creator.nodePickChanged(pick);
		pick.fixed= true;
		pick.x= x; pick.y= y;
		event.consume();
		repaint();
		}
	
	/** Moves the "pick" node to mouse, releases the motionListener.
		Required by MouseListener interface */
	public synchronized void mouseReleased(MouseEvent event) {
		//System.err.println("mouseReleased "+ event);
		int x= event.getX()-translateX, y=event.getY()-translateY;
		removeMouseMotionListener(this);
		if (pick != null) {
			pick.x= x;
			pick.y= y;
			pick.fixed= pickfixed;
			// pick= null;	leave this selected so it can be updated
			}
		event.consume();
		repaint();
		}
	
	/** required by MouseListener interface */
	public void mouseExited(MouseEvent event) {}
	/** required by MouseListener interface */
	public void mouseEntered(MouseEvent event) {}
	/** required by MouseListener interface */
	public void mouseClicked(MouseEvent event) {}
	
	/** required by MouseMotionListener interface */
	public synchronized void mouseMoved(MouseEvent event) {}
	
	/** Adjusts the (x,y) location of the "pick" node to where the mouse is.
		Required by MouseMotionListener interface */
    public synchronized void mouseDragged(MouseEvent event) {
		//System.err.println("mouseDragged "+ event);
		if (pick==null) return;
		int x= event.getX()-translateX, y=event.getY()-translateY;
		pick.x= x;
		pick.y= y;
		repaint();
		event.consume();
		}
	
	/** Creates an initial layout for graphlets. Often quite presentable. */
	private void layoutStarChords() {
		System.err.println("layoutStarChords start");
		waitMessage= "arranging starChords";
		Hashtable<Node,Integer> ht= arrange();
		waitMessage= "laying out starChords";
		Dimension window= getVirtualWindowSize();
		int space= window.width<window.height? window.width : window.height;
		int radius= space/2 - nodeRadius;
		int numNeighbours= ht.size();
		//if (numNeighbours%2==0) numNeighbours++;
		Enumeration<Node> eno= graph.enumNodes();
		while (eno.hasMoreElements()) {
			Node n= eno.nextElement();
			if (n==graph.eigenNode) {
				n.x= 0;  n.y= 0;  /*n.fixed=true;*/ } // central node
			else {
				int neighbourNum= ht.get(n);
				double angle= 2*Math.PI/numNeighbours * neighbourNum;
				n.x= radius*Math.cos(angle);
				n.y= radius*Math.sin(angle);
				}
			}
		System.err.println("layoutStarChords done");
		synchronized(this) { waitMessage= null; }
		}
	
	private Node[] label;	// defines display order for dump();  (underground; TODO: fix!!)
	/** Tries to find a permutation of non-eigen nodes that will minimize the length
		and edge-crossings of edges when laid out in a circle around the eigennode. */
	private Hashtable<Node,Integer> arrange() {
		int size= graph.numNodes();
		if (graph.eigenNode!=null) size--;
		label= new Node[size];
		Hashtable<Node,Integer> ht= new Hashtable<Node,Integer>();
		int next= 0;
		System.err.print("labels: ");
		Enumeration<Node> eno= graph.enumNodes();
		while (eno.hasMoreElements()) {	// build initial table
			Node n= eno.nextElement();
			if (n!=graph.eigenNode) {
				label[next]= n;
				ht.put(n, new Integer(next++));
				System.err.print("   "+n);
				}
			}
		System.err.println();
		dump(ht);
		int dist= traffic(ht);
		System.err.println("~~"+ dist);
		Hashtable<Node,Integer> htKeeper= (Hashtable<Node,Integer>)ht.clone();
		boolean improved= true;
		while (improved) {
			improved= false;
			Enumeration<Node> enumN1= ht.keys();
			while (enumN1.hasMoreElements()) {
				Node n1= enumN1.nextElement();
				Enumeration<Node> enumN2= ht.keys();
				while (enumN2.hasMoreElements()) {
					Node n2= enumN2.nextElement();
					if (n1==n2) continue;
					Integer pos1= ht.get(n1);
					Integer pos2= ht.get(n2);
					ht.put(n1,pos2);
					ht.put(n2,pos1);
					int newDist= traffic(ht);
					if (newDist<dist) { 
						dist= newDist;
						htKeeper= (Hashtable<Node,Integer>)ht.clone(); 
						improved= true;
						//dump(ht);
						//System.err.println("~~"+ newDist);
						}
					ht.put(n1,pos1);
					ht.put(n2,pos2);
					}
				}
			ht= (Hashtable<Node, Integer>) htKeeper.clone();
			}
		dump(ht);
		System.err.println("~~"+ dist);
		return htKeeper;
		}
	
	/** Used to display the permutation implied by a position hashtable.
	It displays positions in the same order as nodes were arranged in the label array. */
	private void dump(Hashtable<Node,Integer> ht) {
		System.err.print("locn[");
		for (int i=0; i<label.length; i++) {
			Node n= label[i];
			//if (n==null) continue;
			//if (n==graph.eigenNode) continue;
			Integer p= ht.get(n);
			System.err.print(" "+p);
			}
		System.err.print(" ]");
		}
	
	// WARNING: underground communicant;  TODO: get rid of this
	private int neighbourEdges;		// # edges between neighbours of eigenNode
	/** Used by arrange() to measure total "length" of neighbour to neighbour edges
		in an arrangement, where "length" is just the distance in the cycle. */
	private int traffic(Hashtable<Node,Integer> ht) {
		int dist=0, cycle=graph.numNodes()-1;
		neighbourEdges= 0;
		Enumeration<Edge> ene= graph.enumEdges();
		while (ene.hasMoreElements()) {
			Edge e= ene.nextElement();
			if (e.to==graph.eigenNode || e.from==graph.eigenNode) continue;
			neighbourEdges++;
			int a= ht.get(e.to);
			int b= ht.get(e.from);
			int diff= a>b? (a-b):(b-a);
			dist+= diff>cycle/2? cycle-diff : diff;
			}
		return dist;
		}
	
	/** Initiates the loop that tries to relax the graph into a better layout. */
    public void start() {
		System.err.println("LayoutMaker start starting");
		while(relaxer!=null) { stop(); Thread.currentThread().yield(); }
		System.err.println("LayoutMaker start going");
		if (true/*graph.partial*/) layoutStarChords();
		else layoutScramble();
		System.err.println("LayoutMaker start finished");
		runRelax();
		repaint();
		}
	
	private void layoutScramble() {
		Enumeration<Edge> ene= graph.enumEdges();
		while (ene.hasMoreElements()) {
			Edge e= ene.nextElement();
			e.len= 100;
			}
		scramble();
		}
	
	/** TODO: Can this be made private? */
	public void runRelax() {
		//System.err.println("runRelax start");
		if (relaxer!=null && relaxing) return;
		relaxer= new Thread(this);
		relaxing= true;
		relaxer.start();
		//System.err.println("LayoutMaker relax started");
		}
	
	/** Terminates the loop that tries to relax the graph into a better layout. */
    public void stop() { relaxing= false; }
	
	}// EOClass LayoutMaker
